Logic
CSE 16: Applied Discrete Mathematics
Instructor: Owen Arden
Winter 2023
The search for truth
How do we know when something is true?
Logic
- Given a premise, we want to reach a
valid conclusion.
- In other words, we want to derive new facts using facts we already
know.
- We want to make an argument supporting our
conclusion without resorting to:
- Our reputation or expertise
- How many other people agree
- Intimidation
Origins
Logic is one of the oldest intellectual disciplines, dating back to
Aristotle
Aristotle’s logic focuses on the idea of
deduction.
- Deduction (as defined by Aristotle):
-
A statement where, given certain assumptions, something different
from these assumptions is also necessarily true.
Origins
Subject : The objects we talk about in a
statement
Predicate : What we say about the
subject
Syllogism : Three statements where the
subject of the first is the predicate of the
second, and the third statement is implied by the first
two.
Origins
- All men are mortal
- Socrates is a man
- Socrates is mortal
Origins
- All men are mortal
- Socrates is a man
- Socrates is mortal
Proposition : A statement that is either
true or false.
Modern logic
In 1879 Gottlob Frege’s publishes Begriffsschrift
- Roughly translated as: “Concept Writing”.
Frege introduces formal notation, some still used (\(\vdash\)).
Defines a propositional calculus in terms of
- 9 axioms (statements assumed to be true)
- 3 inference rules (rules that create new statements
from existing ones)
Propositional calculus
p := "You are a bird."
q := "You have wings."
Compound statements:
- If you are a bird, you have wings: \(p
\implies q\)
- You cannot be a bird and not have wings: \(\neg(p \wedge \neg q)\)
- But bats have wings and are not birds! Is this a
counterexample?
How do we prove \(p \implies q\) is false?
p := "??? is a bird."
q := "??? has wings."
- A counter example to \(p \implies
q\) requires \(p\) to be true
and \(q\) to be false: \(p \wedge \neg q\).
- In other words, is there a bird without wings?
- According to birds.cornell.edu,
all birds have two wings, so we probably won’t find a
counterexample…
- …without a time machine. Moa’s, the only known
wingless bird went extinct ~500 years ago.
![]()
\(p
\implies q\) is not \(q \implies
p\) !!!
p := "??? is a bird."
q := "??? has wings."
- Bats are not birds, but have wings: \(\neg
p \wedge q\)
- To contradict \(p
\implies q\), we would need \(p \wedge
\neg q\).
- \(p \implies q\)
\(\approx\) “If you are a bird, you
have wings.”
- \(q \implies p\)
\(\approx\) “If you have wings, you are
a bird.”
- Bats are a counterexample to
\(q \implies p\), but
not \(p \implies
q\).
Examples from Alice in
Wonderland
“I say what I mean.”
“I see what I eat.”
“I like what I get.”
“I breathe when I sleep.”
“I mean what I say.”
“I eat what I see.”
“I get what I like.”
“I sleep when I breathe.”
![]()
Predicate calculus
Bertrand Russell (Master Bertie) reintroduced Aristotle’s
distinction between subject and
predicate
Some cats do not have fur: \(\exists \text{ cat}.
\text{HasNoFur}(\text{cat})\)
- “There exists a subject (in the set of all cats),
call it \(\text{cat}\), such that \(\text{HasNoFur}(\text{cat})\) is
true.”
- \(\text{HasNoFur}(\cdot)\) is a
predicate that is true when the subject it applies to (\(\text{cat}\)) does not have fur.
All men are mortal: \(\forall \text{
man}. \text{IsMortal}(\text{man})\)
- “For any subject (from the set of all men), call it
\(\text{man}\), \(\text{IsMortal}(\text{man})\) is
true.”
- \(\text{IsMortal}(\cdot)\) is a
predicate that is true when the subject it applies to (\(\text{man}\)) is mortal.
What would Bertie do?
Is this inference correct?
- All X are Y
- Some Y are Z
- Therefore, some X are Z
- Try X=Toyotas, Y=Japanese cars, and Z=made in
America
- All Toyotas are Japanese cars
- Some Japanese cars are made in America
- Therefore, some Toyotas are made in America
- Now try X=Toyotas, Y=cars, and Z=Fiats
- All Toyotas are cars
- Some cars are Fiats
- Therefore, some Toyotas are Fiats
What would Bertie do?
Is this
inference correct? No! This rule is
unsound!!
- All X are Y
- Some X are Z
- Therefore, some X are Z
- Try X=Toyotas, Y=Japanese cars, and Z=made in America
- All Toyotas are Japanese cars
- Some Japanese cars are made in America
- Therefore, some Toyotas are made in America
- Now try X=Toyotas, Y=cars, and Z=Fiats
- All Toyotas are cars
- Some cars are Fiats
- Therefore, some Toyotas are Fiats
![]()
Proofs are
truth-preserving arguments
We need to create new propositions from given
facts.
A sound rule of inference should only
create true conclusions.
A proof, given a set of premises, is just a
sequence of sentences where each element is
- A premise, OR
- The result of applying a sound rule of inference to
earlier members in the sequence
- Once the desired conclusion is added to the
sequence, the proof is complete!
![]()
Axioms : Propositions that you assume to be
true. Ideally, truths that are self-evident.
Rules of inference : Rules that create new
propositions from axioms or other inferred propositions.
Some special names for inferred (proven to be true) propositions:
- Lemma: A statement used to prove other statements
- Theorem: A new statement that is “important”
- Corollary: A special case of a theorem that is useful/popular
Using previously proven Lemmas, Theorems, and Corollaries (plus
axioms), new results can be proven with rules of inference.
Outline
- The Language of Propositions
- Applications
- Translating English Sentences
- System Specifications
- Logic Puzzles
- Logic Circuits
- Logical Equivalences
- Important Equivalences
- Showing Equivalence
- Satisfiability
Proposition or Not?
A proposition is a declarative sentence that is either true
or false.
Sentence:
- Trenton is the capital of New Jersey.
- The Moon is made of green cheese.
Propositional Logic
Notation for constructing propositions
- The proposition that is always
true: \(\textsf{T}\)
- The proposition that is always
false: \(\textsf{F}\)
- Propositional variables: p, q, r, s
- Logical connectives
- Used to construct compound propositions
- Negation \(\neg\)
- Conjunction \(\wedge\)
- Disjunction \(\vee\)
- Implication \(\rightarrow\)
- Biconditional \(\leftrightarrow\)
Truth tables
We can specify the meaning of connectives using truth
tables.
Truth table: A table with the truth-values of
a logical formula for each combination of values of its propositional
variables.
Truth tables were invented by Ludwig Wittgenstein, a student of
Russell’s…
who once alledgedly threatened Karl Popper (another philosopher) with
a fireplace poker.
![]()
Negation
The negation of a proposition \(p\) is written \(\neg p\) and has truth table:
| \(\textsf{T}\) |
\(\textsf{F}\) |
| \(\textsf{F}\) |
\(\textsf{T}\) |
Example: If \(p\)
denotes “The earth is round.”, then \(\neg
p\) denotes “It is not the case that the earth is round.”, or
just “The earth is not round.”
Conjunction
The conjunction of propositions \(p\) and \(q\) is written \(p \wedge q\) and has truth table:
| \(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
| \(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
| \(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{F}\) |
| \(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
Example: If \(p\)
denotes “I am at home.” and \(q\)
denotes “It is raining.” then \(p \wedge
q\) denotes “I am home, and it is raining.”
Disjunction
The disjunction of propositions \(p\) and \(q\) is written \(p \vee q\) and has truth table:
| \(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
| \(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
| \(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
| \(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
Example: If \(p\)
denotes “I am at home.” and \(q\)
denotes “It is raining.” then \(p \vee
q\) denotes “I am home, or it is raining.”
English “or” vs logical “or”
In English, “or” has two distinct meanings.
- Inclusive Or : “Students who have taken MATH 19A or
MATH 19B may take this class.”
- Meaning: Students should have taken one of the pre-reqs, but may
have taken both.
- Exclusive Or : “The entree comes with soup or
salad.”
- Meaning: You can get a soup or a salad with the entree, but not
both.
Which kind of “or” is
disjunction? (\(p \vee
q\))
Exclusive or (XOr)
The exclusive or of propositions \(p\) and \(q\) is written \(p \oplus q\) and has truth table:
| \(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{F}\) |
| \(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
| \(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
| \(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
Example: If \(p\)
denotes “I choose the soup.” and \(q\)
denotes “I choose the salad.” then \(p \oplus
q\) denotes “I choose the soup or I choose the salad.”
Conditional reasoning
- Assume the following premise is true:
- “If I study hard, I will pass CSE 16.”
- Can we infer
- “If I passed CSE 16, then I studied hard.” ?
Conditional reasoning
- Assume the following premise is true:
- “If the company is convicted of fraud, it will go bankrupt.”
- Suppose the company goes bankrupt. Can we infer the company was
convicted of fraud?
Implication
The implication of proposition \(p\) with respect to \(q\) is written \(p \rightarrow q\) and has truth table:
| \(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
| \(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
| \(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{???}\) |
| \(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{???}\) |
Example: If \(p\)
denotes “I am at home.” and \(q\)
denotes “It is raining.” then \(p \rightarrow
q\) denotes “If I am home, then it is raining.”
If I am at home and it is raining, then \(p \rightarrow q\) is
true.
If I am at home and it is not raining, then
\(p \rightarrow q\) is
false.
- What if I am not at home?
Implication
The implication of proposition \(p\) with respect to \(q\) is written \(p \rightarrow q\) and has truth table:
| \(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
| \(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
| \(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{???}\) |
| \(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{???}\) |
Example: If \(x >
2\) then \(x^2 > 4\).
- More formally, let \(P(x)
= x > 2\) and \(Q(x) = x^2 >
4\). Is \(P(x) \rightarrow
Q(x)\) true for any \(x\)?
- What if \(x=1\)?
\(P(1)\) is false and \(Q(1)\) is false.
- What if \(x=-5\)?
\(P(-5)\) is false and \(Q(-5)\) is true.
Implication
The implication of proposition \(p\) with respect to \(q\) is written \(p \rightarrow q\) and has truth table:
| \(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
| \(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
| \(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
| \(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
Example: If \(x >
2\) then \(x^2 > 4\).
- We say that \(P(x)
\rightarrow Q(x)\) is true since you will never
find a value of \(x\) such that \(x > 2\) and \(x^2 < 4\).
- Therefore in the truth table, whenever \(p\) is false, \(p
\rightarrow q\) is true, regardless of the value
of \(q\).
Implication \(\neq\) causation
- “If I use the power of Grayskull to make it true, then \(1+1=2\).”
- Intuitively, this statement seems false, or at least fishy.
- \(1+1=2\) is true by the laws of
math, not by the power of Grayskull.
- Mathematically, the statement is true.
- The requirement is to prove the conclusion true, whether we use the
premise or not is irrelevant.
- So say the line, He-Man: “By the power of Grayskull, 1+1=2!”
Implication as a promise
- You could view the logical conditional as an obligation.
- “If I am elected, then I will fund affordable housing.”
- If the politician is elected and does not fund affordable
housing, then they have broken their campaign pledge.
- In this case \(p=\textsf{T}\) (“I
am elected.”), but \(q=\textsf{F}\) (“I
did not fund affordable housing.”).
- If the politician is not elected then no promises
are broken.
Understanding implication
In \(p \rightarrow q\) there
doesn’t need to be any connection between the antecedent (\(p\)) or the consequent (\(q\)).
The “meaning” of \(p \rightarrow
q\) only depends on the truth values of \(p\) and \(q\).
Recognizing implication
- All of these are ways of expressing \(p
\rightarrow q\):
if \(p\)
then \(q\)
if \(p\), \(q\)
\(q\), unless \(\neg p\)
\(q\) if \(p\)
\(q\) whenever
\(p\)
\(q\) follows from
\(p\)
\(p\) implies \(q\)
\(q\) only if \(p\)
\(q\) when \(p\)
\(p\) is sufficient
for \(q\)
\(q\) is necessary
for \(p\)
a sufficient condition for \(q\) is \(p\)
a necessary condition for \(p\) is \(q\)
Recognizing implication
- Write as an implication \(p \rightarrow
q\)
- What are \(p\) and \(q\) ?
- Why does he want to know \(q\) when
\(\neg p\)?
Biconditional
If \(p\) and \(q\) are propositions, the we can form the
biconditional proposition \(p
\leftrightarrow q\), read as “\(p\) if and only if \(q\)”, with truth table:
| \(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
| \(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
| \(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{F}\) |
| \(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
Example: If \(p\)
denotes “I am at home.” and \(q\)
denotes “It is raining.” then \(p
\leftrightarrow q\) denotes “I am home if and only if it is
raining.”
Recognizing biconditionals
- Ways of expressing \(p \leftrightarrow
q\):
\(p\) if and only
if \(q\)
\(p\) is necessary and
sufficient for \(q\)
if \(p\)
then \(q\),
and conversely
\(p\) iff \(q\)
Should you honk if
their light is green?
![]()
- If you honk, then you love formal logic.
- If you love formal logic, then you honk.
Tautologies and
contradictions
Tautology: a proposition that is always
true.
- Example: \(p \vee \neg p\)
Contradiction: a proposition that is always
false.
- Example: \(p \wedge \neg p\)
| \(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{F}\) |
| \(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{F}\) |
Converse, inverse,
contrapositive
Converse: The converse of \(p \rightarrow q\) is \(q \rightarrow p\).
Inverse: The inverse of \(p \rightarrow q\) is \(\neg p \rightarrow \neg q\).
Contrapositive: The contrapositive of
\(p \rightarrow q\) is \(\neg q \rightarrow \neg p\).
| \(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
| \(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{F}\) |
| \(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
| \(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
Converse, inverse,
contrapositive
Notice anything about that last column (the contrapositive)?
It had the same values as \(p \rightarrow
q\)!
That means the contrapositive of \(p
\rightarrow q\) is logically equivalent!
Truth tables are a good way to show logical equivalence (and
non-equivalence). Which of the below formulas are
equivalent?
| \(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
| \(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
| \(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{F}\) |
| \(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
Logical equivalence
Logically equivalent: Two propositions \(p\) and \(q\) are logically equivalent iff
\(p \leftrightarrow q\) is a
tautology.
We write equivalence as \(P
\Leftrightarrow Q\) or \(P \equiv
Q\) where \(P\) and \(Q\) are compound propositions.
If \(P\) and \(Q\)’s truth tables agree, they are
equivalent!
| \(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
| \(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
| \(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{F}\) |
| \(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
Proving De Morgan’s Second
Law
De Morgan’s Second Law: \[ \neg (p \wedge q) \equiv \neg p \vee \neg
q\] \[ \neg (p \vee q) \equiv \neg p
\wedge \neg q\]
| \(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
| \(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
| \(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
| \(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
Laws of propositional logic
We fully can axiomatize (specify the axioms / assumptions
of) propositional logic using similar equivalences.
| Idempotence |
\(p \vee p \equiv p\) |
\(p \wedge p
\equiv p\) |
| Associativity |
\((p \vee q) \vee r \equiv p \vee (q \vee
r)\) |
\((p \wedge q)
\wedge r \equiv p \wedge (q \wedge r)\) |
| Commutativity |
\(p \vee q \equiv q \vee p\) |
\(p \wedge q
\equiv q \wedge p\) |
| Distributivity |
\(p \vee (q \wedge r) \equiv (p \vee q)
\wedge (p \vee r)\) |
\(p \wedge (q
\vee r) \equiv (p \wedge q) \vee (p \wedge r)\) |
| Identity |
\(p \vee \textsf{F} \equiv p\) |
\(p \wedge
\textsf{T} \equiv \textsf{T}\) |
| Domination |
\(p \wedge \textsf{F} \equiv
\textsf{F}\) |
\(p \vee
\textsf{T} \equiv \textsf{T}\) |
| Dbl negation |
\(\neg \neg p \equiv p\) |
|
| Complement |
\(p \wedge \neg p \equiv
\textsf{F}\)
\(~~~~~~\neg
\textsf{T} \equiv \textsf{F}\) |
\(p \vee \neg p
\equiv \textsf{T}\)
\(\neg
\textsf{F} \equiv \textsf{T}\) |
| De Morgans |
\(\neg (p \vee q) \equiv \neg p \wedge
\neg q\) |
\(\neg (p
\wedge q) \equiv \neg p \vee \neg q\) |
| Absorption |
\(p \vee (p \wedge q) \equiv
p\) |
\(p \wedge (p
\vee q) \equiv p\) |
| Conditional identity |
\(p \rightarrow q \equiv \neg p \vee
q\) |
\(p
\leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow
p)\) |
Predicates and quantifiers
Generalizing
relationships between propositions
Propositional example:
- If Jack knows Jill, then Jill knows Jack.
- Jack knows Jill.
- Does Jill know Jack?
- What about other people?
- If Calvin knows Hobbes, then Hobbes knows
Calvin.
- If Charlie knows Lucy, then Lucy knows
Charlie.
- …
How can we say “If one person knows another, then the second person
knows the first.” without needing a proposition for every
person?
Predicate logic
Predicate logic adds new features to propositional logic:
Variables: \(x\), \(y\), \(z\)
Predicates: “\(x\) is even”,
“\(x^n + y^n\) = z^n”
Propositional functions: \(P(x)\), \(M(x,y,z)\)
Quantifiers: \(\forall\)
“for all”, \(\exists\)
“there exists”
Defining propositional
functions
Predicate: A logical statement whose truth
value depends on one or more variables.
Domain: The set of all possible values for
a variable.
Propositional function: A generalization
of a proposition defined by a predicate which becomes a proposition
when the predicate’s variables are replaced by elements from their
domain.
Defining propositional
functions
Example: Let the domain of \(x\) be the integers. \[P(x) := x > 0\]
- \(P(-3)\) is false.
- \(P(0)\) is true.
- \(P(3)\) is true.
- \(P(x)\) is not a proposition.
- \(P(z)\) is not a proposition.
Quantifiers
Quantifiers let us talk about all or some
(i.e., at least one) of the elements in a variable’s
domain.
Around since Frege, but notation and popularization due mostly to his
contemporary Peirce.
![]()
Charles Peirce (1839-1914)
Universal quantification: \(\forall\)
Universal quantification: \(\forall x. P(x)\) reads “For all \(x\), \(P\)
of \(x\).” and asserts that \(P(x)\) is true for every
\(x\) in the domain.
Example: Let the domain of \(x\) be the integers.
- Let \(P(x) := |x| \geq 0\) \[\forall x. P(x) \text{ is true.}\]
- Let \(P(x) := x \geq 0\) \[\forall x. P(x) \text{ is false.}\]
Existential quantification:
\(\exists\)
Existential quantification: \(\exists x. P(x)\) reads “There exists an
\(x\) such that \(P\) of \(x\).” and asserts that \(P(x)\) is true for at least
one \(x\) in the domain.
Example: Let the domain of \(x\) be the integers.
- Let \(P(x) := x \geq 0\) \[\exists x. P(x) \text{ is true.}\]
- Let \(P(x) := |x| \lt 0\) \[\exists x. P(x) \text{ is false.}\]
Uniqueness quantification:
\(\exists!\)
Uniqueness quantification: \(\exists! x. P(x)\) reads “There is a unique
\(x\) such that \(P\) of \(x\).” and asserts that \(P(x)\) is true for one and only
one \(x\) in the domain.
Example: Let the domain of \(x\) be the integers.
- Let \(P(x) := x + 1 = 0\) \[\exists! x. P(x) \text{ is true.}\]
- Let \(P(x) := x + 1 \leq 0\) \[\exists! x. P(x) \text{ is false.}\]
Uniqueness quantification:
\(\exists!\)
Uniqueness quantification: \(\exists! x. P(x)\) reads “There is a unique
\(x\) such that \(P\) of \(x\).” and asserts that \(P(x)\) is true for one and only
one \(x\) in the domain.
Uniqueness is actually derivable in terms of \(\forall\), \(\exists\), and equality (\(=\)). \[\exists!
x . P(x) \equiv \exists x . (P(x) \wedge \forall y . P(y) \rightarrow y
= x)\]
Variable scope
Variables have a scope just like in a programming
language.
In predicate logic, the scope of a variable is defined by a
quantifier.
Occurrences of a variable within a quantifier’s scope are called
bound. Occurrences which are not bound are called
free.
Example: \[\exists y.
P(x,y)\] Here \(x\) is free and
\(y\) is bound.
Quantifier intuition
One way to understand quantifiers is to think about the
finite case.
- Let’s assume the domain of \(x\) is finite and consider how we might
evaluate the truth value of \[\forall x.
P(x)\]
- Loop through all possible values of \(x\).
- If \(P(x)\) is
true for each value of \(x\), then \(\forall x. P(x)\) is
true.
- Otherwise \(\forall x.
P(x)\) is false.
- Similar to a list of ANDs, one for each value of
\(x\) \((P(x_0) \wedge P(x_1) \wedge~...)\)
Quantifier intuition
One way to understand quantifiers is to think about the
finite case.
- Let’s assume the domain of \(x\) is finite and consider how we might
evaluate the truth value of \[\exists x.
P(x)\]
- Loop through all possible values of \(x\).
- If \(P(x)\) is
false for each value of \(x\), then \(\exists x. P(x)\) is
false.
- Otherwise \(\exists x.
P(x)\) is true.
- Similar to a list of ORs, one for each value of
\(x\) \((P(x_0) \vee P(x_1) \vee~...)\)
Negating quantified
statements
Notice how our algorithms seemed similar, but opposite to each other?
These equivalences make that explicit:
\[ \neg \forall x . P(x) \equiv \exists x.
\neg P(x)\]
\[ \neg \exists x . P(x) \equiv \forall x.
\neg P(x)\]
To get why, think about De Morgan’s Law:
\[\neg (P(x_0) \wedge P(x_1) \wedge~...)
\equiv (\neg P(x_0) \vee \neg P(x_1) \vee ~...)\]
\[\neg (P(x_0) \vee P(x_1) \vee~...)
\equiv (\neg P(x_0) \wedge \neg P(x_1) \wedge~...)\]
Recognizing quantification
- “Every student in the class has taken a Python course.”
- Domain?
- Formal statement?
Define \(P(x)\) to be “\(x\) has taken a Python course.” where the
domain of \(x\) is the set of students
in the class. \[ \forall x.
P(x) \]
Negating the statement gives “Is it not the case that every student
in the class has taken Python.” \[ \neg
\forall x. P(x) \]
Or put another way, “There is a student in the class who has not
taken Python.” \[ \exists x. \neg
P(x) \]
Recognizing quantification
- “There is a student in the class who has taken a Python
course.”
Negating the statement gives “it not the case that there is a student
in the class who has taken a Python course.” \[ \neg \exists x. P(x) \]
Or put another way, “Every student in the class has not taken a
Python course.” \[ \forall x. \neg
P(x) \]
Nested quantifiers
Nested quantifiers are often necessary to express concepts.
Example: “Every real number has an inverse.”
\[\forall x \exists y.
(x+y=0)\]
- Propositional functions can also be nested:
- Let \(Q(x) := \exists y. P(x,
y)\)
- Let \(P(x,y) := x + y = 0\)
Order of quantifiers
Is \(\exists y \forall x\) the same
as \(\forall x \exists y\)?
Consider \(P(x,y) := y\) is a soul
mate of \(x\).
- Translate to English: \(\exists y. \forall x . P(x, y)\)
- “There exists a \(y\) that is the soulmate of every \(x\).”
- Translate to English: \(\forall x . \exists y . P(x, y)\)
- “For every \(x\)
there exists a \(y\) that is the
soulmate of \(x\).”
- Translate to English: \(\forall x . \exists! y . P(x, y)\)
- “For every \(x\)
there exists a unique \(y\) that is the soulmate of \(x\).”
Order of quantifiers
Examples:
- Let \(P(x, y) := x+y =
y+x\), where the domain of \(x\)
and \(y\) is the real numbers. \[ \forall x \forall y. P(x, y) \equiv? ~~ \forall
y \forall x. P(x, y)\]
- Let \(Q(x, y) := x+y =
0\), where the domain of \(x\)
and \(y\) is the real numbers. \[ \forall x \exists y. Q(x, y) \equiv? ~~ \exists
y \forall x. Q(x, y)\]
More quantifier order
practice
Let \(P(x, y) := x \cdot y = 0\)
where \(x\) and \(y\) are real numbers.
- \(\forall x. \forall y.
P(x,y)\)
- \(\forall x. \exists y.
P(x,y)\)
- \(\exists x. \forall y.
P(x,y)\)
- \(\exists x. \exists y.
P(x,y)\)
More quantifier order
practice
Let \(P(x, y) := x / y = 1\) where
\(x\) and \(y\) are real numbers.
- \(\forall x. \forall y.
P(x,y)\)
- \(\forall x. \exists y.
P(x,y)\)
- \(\exists x. \forall y.
P(x,y)\)
- \(\exists x. \exists y.
P(x,y)\)
Recognizing nested
quantification
| \(\forall x
\forall y. P(x, y)\) \(\forall y
\forall x. P(x, y)\) |
\(P(x,y)\) is true for every pair \(x,y\). |
There is at least on pair \(x,y\) for which \(P(x,y)\) is false. |
| \(\forall x
\exists y. P(x, y)\) |
For every \(x\) there is a \(y\) for which \(P(x,y)\) is true. |
There is an \(x\) such that \(P(x,y)\) is false for every \(y\). |
| \(\exists x
\forall y. P(x, y)\) |
There is an \(x\) for which \(P(x,y)\) is true for every \(y\). |
For every \(x\) there is a \(y\) for which \(P(x,y)\) is false. |
| \(\exists x
\exists y. P(x, y)\) \(\exists y
\exists x. P(x, y)\) |
There is a pair \(x,y\) for which \(P(x,y)\) is true. |
\(P(x,y)\) is false for every pair \(x,y\) |
Negating nested
quantification
Recall De Morgan’s laws for quantifiers:
\[ \neg \forall x . P(x) \equiv \exists x.
\neg P(x)\]
\[ \neg \exists x . P(x) \equiv \forall x.
\neg P(x)\]
Let’s apply these laws to a statement with nested quantifiers.
- Write a statement for “There does not exist a
person who has taken a flight on every airline in the world.”
- Let \(P(p,f) :=\)
“\(p\) has taken flight \(f\)”, where \(p\) has domain people, and \(f\) has domain flights.
- Let \(Q(f,a) :=\)
“Flight \(f\) is operated by \(a\).”, where \(a\) has domain airlines, and \(f\) has domain flights.
\[\neg \exists p . \forall a . \exists f .
P(p,f) \wedge Q(f,a)\]
Negating nested
quantification
Now let’s use De Morgan’s Laws to move the negation as far “inwards”
as possible.
\(\neg \exists p .
\forall a . \exists f . P(p,f) \wedge Q(f,a)\)
\(\forall p . \neg
\forall a . \exists f . P(p,f) \wedge Q(f,a)\) by De Morgan’s
for \(\exists\)
\(\forall p . \exists
a . \neg \exists f . P(p,f) \wedge Q(f,a)\) by De Morgan’s
for \(\forall\)
\(\forall p . \exists
a . \forall f . \neg (P(p,f) \wedge Q(f,a))\) by De Morgan’s
for \(\exists\)
\(\forall p . \exists
a . \forall f . \neg P(p,f) \vee \neg Q(f,a)\) by De Morgan’s
for \(\exists\)
“For every person there is an airline such that for all flights,
the person has not taken that flight or that flight is not on that
airline.”
More translation practice
Example:
Let \(x,y,z\) have domain of the
students in your school.
Let \(C(x) :=\) “\(x\) has a computer.”
Let \(F(x,y) :=\) “\(x\) and \(y\) are friends.”
- Translate: \(\forall x .
C(x) \vee (\exists y. C(y) \wedge F(x,y))\)
- Answer: “Every student in your
school has a computer or has a friend who has a computer.”
- Translate: \(\exists x
.\forall y. \forall z. (F(x,y) \wedge F(x,z) \wedge (y \neq z))
\rightarrow \neg F(y,z)\)
- Answer: “There is a student with
no friends that are also friends with each other.”
More translation practice
- Example 1: “Brothers are
siblings.”
- Solution: \(∀x.∀y.(B(x,y)
→ S(x,y))\)
- Example 2: “Siblinghood is
symmetric.”
- Solution: \(∀x.∀y.(S(x,y)
→ S(y,x))\)
- Example 3: “Everybody loves
somebody.”
- Solution: \(∀x.∃y.L(x,y)\)
- Example 4: “There is someone who
is loved by everyone.”
- Solution: \(∃y.∀x.L(x,y)\)
- Example 5: “There is someone who
loves someone.”
- Solution: \(∃x.∃y.L(x,y)\)
- Example 6: “Everyone loves
themselves”
Translating mathematical
statements
Example: Translate “The sum of two positive integers
is always positive” into an expression in predicate logic.
- Rewrite to make quantifiers and domains explicit:
- “For every two integers, if these integers are both
positive, then the sum of the integers is positive.”
- Rewrite to use variables and specify their domain:
- “For all positive integers \(x\) and \(y\), \(x+y\) is positive.”
- Now replace the English phrases with the
appropriate notation.
- \(\forall x . \forall y .
(x > 0 \wedge y > 0) \rightarrow (x+y > 0)\) where \(x,y\) have domain of (all) integers.
Example from Calculus
(of infinitesimals):
Limit: Let \(f\) be a function defined on some open
interval that contains the number \(a\), except possibly at \(a\) itself. Then we say that the
limit of \(f(x)\) as \(x\) approaches \(a\) is \(L\), and we write
\[\lim _{x \to a} f(x)=L\] if for
every number \(\varepsilon > 0\)
there is a number \(\delta > 0\)
such that \[\text{if } 0 < |x - a|
< \delta \text{ then } |f(x) - L| < \varepsilon\]
We can use quantifiers to express the definition of the limit of a
real-valued function \(f(x)\) of a real
variable \(x\) at a point \(a\) in its domain.
\[\forall \varepsilon . \exists \delta .
\forall x . (0 < |x - a| < \delta \rightarrow |f(x) - L| <
\varepsilon)\]
where the domain of \(\varepsilon\)
and \(\delta\) is the positive reals
and the domain of \(x\) is all
reals.
Reasoning about Calculus
with logic
How could we use our logical definition of limits to express that the
limit of \(f(x)\) as \(x\) approaches \(a\) does not exist?
- We need to say that for all real numbers \(L\), \[ \neg
\forall \varepsilon . \exists \delta . \forall x . (0 < |x - a| <
\delta \rightarrow |f(x) - L| < \varepsilon)\]
- Move the negation in
\(\equiv \exists
\varepsilon . \neg \exists \delta . \forall x . (0 < |x - a| <
\delta \rightarrow |f(x) - L| < \varepsilon)\)
\(\equiv \exists
\varepsilon . \forall \delta . \neg \forall x . (0 < |x - a| <
\delta \rightarrow |f(x) - L| < \varepsilon)\)
\(\equiv \exists
\varepsilon . \forall \delta . \exists x . \neg (0 < |x - a| <
\delta \rightarrow |f(x) - L| < \varepsilon)\)
\(\equiv \exists
\varepsilon . \forall \delta . \exists x . \neg ( \neg (0 < |x - a|
< \delta) \vee |f(x) - L| < \varepsilon)\)
\(\equiv \exists
\varepsilon . \forall \delta . \exists x . 0 < |x - a| < \delta
\wedge \neg (|f(x) - L| < \varepsilon)\)
\(\equiv \exists
\varepsilon . \forall \delta . \exists x . 0 < |x - a| < \delta
\wedge |f(x) - L| \geq \varepsilon\)
Reasoning about Calculus
with logic
- Quantify over all real numbers \(L\):
- \(\forall L. \exists
\varepsilon . \forall \delta . \exists x . 0 < |x - a| < \delta
\wedge |f(x) - L| \geq \varepsilon\)
- Translating back to English:
- For every real number \(L\), there is a real number \(\varepsilon > 0\), such that for every
real number \(\delta > 0\), there
exists a real number \(x\) such that
\(0 < |x - a| < \delta\) and
\(|f(x) - L| \geq \varepsilon\).
Recap
Tautology: a proposition that is always
true.
- Example: \(p \vee \neg p\)
Contradiction: a proposition that is always
false.
- Example: \(p \wedge \neg p\)
Logically equivalent: Two propositions \(p\) and \(q\) are logically equivalent,
written \(p \equiv q\), iff \(p \leftrightarrow q\) is a tautology.
Proof technique
So far we have only proven tautologies, contradictions, and
equivalence using truth tables. This approach is not scalable.
With \(n\) variables, there are
\(2^n\) truth assignments. Worse,
truth tables cannot be used with quantifiers and infinite
sets!
| \(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
| \(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{F}\) |
| \(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
| \(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
| \(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
| \(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{F}\) |
| \(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
| \(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
Deriving new
propositions from existing ones
How can we get new conclusions from existing premises without
enumerating all truth values?
IDEA: Can we manipulate logical statements
symbolically using axioms and inference rules to obtain a proof
of the desired conclusion?
Proofs according to
Logicomix
A proof is the verification of a a mathematical
statement starting from a set of agreed-upon first
principles proceeding by unambiguous and unabridged
logical steps or rules of inference.
- What are agreed-upon first principles?
- Axioms or proven statements
derived from these axioms.
Theorems
Theorem: any inference obtained from
- a set of premises: \(\Gamma\)
- axioms or previously proven theorems
- the rules of inference
Notation:
- \(\Gamma \vdash \alpha\)
- \(\vdash \alpha\) (no premises,
\(\Gamma\) is empty)
- Zybook style: \[\frac{\Gamma}{\therefore
\alpha}\]
Zybook also calls theorems valid arguments.
Example: Hilbert’s system
- Small set of axioms and rules of inference from which all theorems
can be derived.
Three axioms:
(actually 4 originally, but one turned out to be
redundant) \[\begin{align}
A1&: \alpha \to (\beta \to \alpha) \\
A2&: (\alpha \to (\beta \to \gamma)) \to ((\alpha \to \beta) \to
(\alpha \to \gamma)) \\
A3&: (\neg \alpha \to \neg \beta) \to (\beta \to \alpha) \\
\end{align}
\]
One inference rule: Modus Ponens \[ p, p \to q \vdash q \]
From which all theorems of propositional logic can
be derived!
Hilbert’s Axioms are tautologies!
Can you prove it?
| \(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
| \(\textsf{T}\) |
\(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
| \(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
| \(\textsf{F}\) |
\(\textsf{F}\) |
\(\textsf{T}\) |
\(\textsf{T}\) |
Prove an axiom?
Wondering how they figured out one of the axioms was redundant?
They proved it could be derived from the other axioms!
\[\begin{align}
A1&: \alpha \to (\beta \to \alpha) \\
A2&: (\alpha \to (\beta \to \gamma)) \to ((\alpha \to \beta) \to
(\alpha \to \gamma)) \\
A3&: (\neg \alpha \to \neg \beta) \to (\beta \to \alpha) \\
\end{align}\]
Goal: Derive \(\vdash \alpha \to
\alpha\) using only axioms and modus ponens.
\[\begin{align}
& p \to ((q \to p) \to p) \tag{1}\\
& \quad \quad \text{A1 with } \alpha = p \text{ and } \beta = (q \to
p). \\
& (p \to ((q \to p) \to p) \to ((p \to (q \to p)) \to (p \to p)))
\tag{2} \\
& \quad \quad \text{A2 with } \alpha = p \text{ and } \beta = (q \to
p) \text{ and } \gamma = p. \\
& (p \to (q \to p)) \to (p \to p) \tag{3} \\
& \quad \quad \text{ modus ponens using (1) and (2)} \\
& (p \to (q \to p)) \tag{4} \\
& \quad \quad \text{ A1 with } \alpha = p \text{ and } \beta = q \\
& p \to p \\
& \quad \quad \text{ modus ponens using (3) and (4)} \\
\end{align}\]
Prove an inference rule?
Show it is a valid argument (is a theorem)!
Consider this argument: \[\alpha \to
\beta, \beta \to \gamma \vdash \alpha \to \gamma\]
What do we need to prove to show this argument is a theorem?
In general \[p_0, ..., p_n \vdash
q\] is valid (true for all truth values of \(p_i\) and \(q\)) if \[(p_0
\wedge ... \wedge p_n) \to q\] is a tautology.
Proof
\[\alpha \to \beta, \beta \to \gamma
\vdash \alpha \to \gamma\]
\[\begin{align}
A1&: \alpha \to (\beta \to \alpha) \\
A2&: (\alpha \to (\beta \to \gamma)) \to ((\alpha \to \beta) \to
(\alpha \to \gamma)) \\
A3&: (\neg \alpha \to \neg \beta) \to (\beta \to \alpha) \\
\end{align}\]
\[\begin{align}
(1) & \beta \to
\gamma &
\text{Premise}\\
(2) & (\beta \to \gamma) \to (\alpha \to (\beta \to
\gamma)) & \text{A1}\\
(3) & \alpha \to (\beta \to
\gamma) &
\text{MP w/ (1),(2)}\\
(4) & (\alpha \to (\beta \to \gamma)) \to ((\alpha \to \beta) \to
(\alpha \to \gamma)) & \text{A2}\\
(5) & (\alpha \to \beta) \to (\alpha \to
\gamma) & \text{MP w/
(3),(4)}\\
(6) & \alpha \to
\beta &
\text{Premise}\\
(7) & \alpha \to
\gamma &
\text{MP w/ (5),(6)}
\end{align}\]
Notice: Every line is either a premise, an instance
of an axiom, or the result of applying a theorem or rule (e.g., MP) to
previous line(s).
Some valid (and useful) rules
| \(p,p \to q
\vdash q\) |
Modus ponens |
| \(\neg q,p \to q
\vdash \neg p\) |
Modus tollens |
| \(q\vdash p \vee
q\) |
Addition (L) |
| \(p\vdash p \vee
q\) |
Addition (R) |
| \(p \wedge
q\vdash p\) |
Simplification (L) |
| \(p \wedge
q\vdash q\) |
Simplification (R) |
| \(p, q\vdash p
\wedge q\) |
Conjunction |
| \(p \to q, q \to
r \vdash p \to r\) |
Hypothetical syllogism |
| \(p \vee q, \neg
p \vdash q\) |
Disjunctive syllogism |
| \(p \vee q, \neg
p \vee r \vdash q \vee r\) |
Resolution |
Back to Aristotle
What about quantifiers?
- We can express Aristotle’s example\(^*\) in predicate logic as the following
argument:
\[
\begin{prooftree}
\AxiomC{$\forall x. \text{Human}(x) \to \text{Mortal}(x)$}
\AxiomC{$\text{Human}(\text{Socrates})$}
\BinaryInfC{$\therefore \text{Mortal}(\text{Socrates})$}
\end{prooftree}
\]
or
\[\forall x. \text{Human}(x) \to
\text{Mortal}(x), \text{Human}(\text{Socrates})
\vdash \text{Mortal}(\text{Socrates})\]
- Is this a valid argument?
\(*\): updated to be slightly
less gender-biased
Universal Instantiation (UI)
\[\begin{prooftree}
\AxiomC{$\forall x. P(x)$}
\UnaryInfC{$\therefore P(c)$}
\end{prooftree}\]
\[\forall x.P(x) \vdash P(c)\]
where \(c\) is from the domain of
\(x\).
Example: For the domain of all dogs, where Thornton
is a dog.
- Suppose “All dogs are cuddly.”
- Therefore, “Thornton is cuddly.”
Universal Generalization (UG)
\[\begin{prooftree}
\AxiomC{$P(c)$}
\UnaryInfC{$\therefore \forall x. P(x)$}
\end{prooftree}\]
\[P(c) \vdash \forall x.P(x)\]
where \(c\) is an arbitrary
element from the domain of \(x\).
This is often left implicit in proofs when a statement has been
proven in terms of an arbitrary element.
Example: Consider an arbitrary natural number \(n\).
- \(n \geq 0\) (by definition)
- Therefore, \(\forall x. x \geq
0\)
Existential Instantiation
(EI)
\[\begin{prooftree}
\AxiomC{$\exists x. P(x)$}
\UnaryInfC{$\therefore P(c)$}
\end{prooftree}\]
\[P(c) \vdash \exists x.P(x)\]
for some element \(c\) in the domain
of \(x\)
(but you don’t know
which one).
Example:
- “There is someone who got a ticket to Taylor Swift.”
- Let’s call them TayFan and say: “TayFan got a ticket.”
- “There is someone who got 2 tickets to Taylor
Swift.”
- Can we say “TayFan got 2 tickets.”?
- No, because it may or may not be the same
person.
- Instead we call this one TayFan2 and say “TayFan2
got 2 tickets.”
Existential Generalization
(EG)
\[\begin{prooftree}
\AxiomC{$P(c)$}
\UnaryInfC{$\therefore \exists x. P(x)$}
\end{prooftree}\]
\[P(c) \vdash \exists x.P(x)\]
for some element \(c\) in the domain
of \(x\)
(but you may or may not
know which one).
Example:
- “Michelle got tickets to Taylor Swift.”
- “Therefore, someone got tickets to Taylor Swift.”
Michelle would sometimes be called the “witness” to the existential
since her existence proves the quantified statement.
Back to Socrates’ Mortality
\[
\begin{prooftree}
\AxiomC{$\forall x. \text{Human}(x) \to \text{Mortal}(x)$}
\AxiomC{$\text{Human}(\text{Socrates})$}
\BinaryInfC{$\therefore \text{Mortal}(\text{Socrates})$}
\end{prooftree}
\]
\[\begin{align}
& \forall x. \text{Human}(x) \to \text{Mortal}(x)
&(1)&\quad\quad \text{Premise}\\
& \text{Human}(\text{Socrates}) \to \text{Mortal}(\text{Socrates})
&(2)&\quad\quad \text{UI},(1)\\
& \text{Human}(\text{Socrates})
&(3)&\quad\quad \text{Premise}\\
& \text{Mortal}(\text{Socrates})
&&\quad\quad \text{MP},(3),(2)
\end{align}\]
\[
\begin{prooftree}
\AxiomC{$\forall x. \text{Human}(x) \to \text{Mortal}(x)$}
\RightLabel{(UI)}
\UnaryInfC{$\text{Human}(\text{Socrates}) \to
\text{Mortal}(\text{Socrates})$}
\AxiomC{$\text{Human}(\text{Socrates})$}
\RightLabel{(MP)}
\BinaryInfC{$\therefore \text{Mortal}(\text{Socrates})$}
\end{prooftree}
\]
More practice
Example: Suppose:
- “A student in the class has not read the book.”
- “Everyone in the class passed the exam.”
Construct a valid argument (prove) that the following conclusion
follows from these premises.
Solution:
Define:
- \(C(x)\) to be “\(x\) is in the class.”
- \(B(x)\) to be “\(x\) has read the book.”
- \(P(x)\) to be “\(x\) passed the exam.”
More practice
- Formally, we wish to prove \[\begin{prooftree}
\AxiomC{$\exists x. C(x) \wedge \neg B(x)$}
\AxiomC{$\forall x. C(x) \to P(x)$}
\BinaryInfC{$\therefore \exists x. P(x) \wedge \neg B(x)$}
\end{prooftree}
\]
\[\begin{align}
(1) \quad \quad &\exists x. C(x) \wedge \neg
B(x) &\text{Premise}\\
(2) \quad \quad &C(a) \wedge \neg B(a) &\text{EI on
(1)}\\
(3) \quad \quad
&C(a) &\text{Simplification (L) on
(2)}\\
(4) \quad \quad &\forall x. C(x) \to
P(x) &\text{Premise}\\
(5) \quad \quad &C(a) \to P(a) &\text{UI on
(4)}\\
(6) \quad \quad &P(a) &\text{MP
from (3) and (5)}\\
(7) \quad \quad &\neg
B(a) &\text{Simplification (R) on (2)}\\
(8) \quad \quad &P(a) \wedge \neg
B(a) &\text{Conjunction on (6) and (7)}\\
(9) \quad \quad &\exists x. P(x) \wedge \neg B(x) &\text{EG
from (8)}\\
\end{align}\]
Proof tree version
\[\begin{prooftree}
\AxiomC{$\exists x. C(x) \wedge \neg B(x)$}
\RightLabel{(EI)}
\UnaryInfC{$C(a) \wedge \neg B(a)$}
\RightLabel{(Simpl)}
\UnaryInfC{$C(a)$}
\AxiomC{$\forall x. C(x) \to P(x)$}
\RightLabel{(UI)}
\UnaryInfC{$C(a) \to P(a)$}
\RightLabel{(MP)}
\BinaryInfC{$P(a)$}
\AxiomC{$\exists x. C(x) \wedge \neg B(x)$}
\RightLabel{(EI)}
\UnaryInfC{$P(a) \wedge \neg B(a)$}
\RightLabel{(Simpl)}
\UnaryInfC{$\neg B(a)$}
\RightLabel{(Conj)}
\BinaryInfC{$P(a) \wedge \neg B(a)$}
\RightLabel{(EG)}
\UnaryInfC{$\exists x. P(x) \wedge \neg B(x)$}
\end{prooftree}
\]
Valid Quantifier Rules
| \(\forall x.P(x)
\vdash P(c)\) |
\(c\) is
an element in domain of \(P\) |
Universal Instantiation |
| \(P(c) \vdash
\forall x.P(x)\) |
\(c\) is
an arbitrary element in domain of \(P\) |
Universal Generalization |
| \(\exists x.P(x)
\vdash P(c)\) |
\(c\) is
a “fresh” name for some particular element in domain of \(P\) |
Existential Instantiation |
| \(P(c) \vdash
\exists x.P(x)\) |
\(c\) is
a particular element in domain of \(P\) |
Existential Generalization |
Charles Peirce (1839-1914)
